function maxProfit(prices: number[]): number {
  // 1. 定义状态: dp[i]
  // * 到i天能获取到的最大收益是多少
  // 2. 状态转移方程
  // dp[i] = max(dp[i-1], prices[i] - minPrice)
  // 3. 初始化状态: dp[0] = 0
  // 4. 获取最后一次的值 dp[n-1]
  const n = prices.length;
  if (n < 2) return 0;

  let prev = 0;
  let minPrice = prices[0];

  for (let i = 1; i < n; i++) {
    prev = Math.max(prices[i] - minPrice, prev);
    minPrice = Math.min(minPrice, prices[i]);
  }

  return prev;
}
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // 5

export {};
